package com.demo.java.OD401_450.OD426;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【部门人力分配(C&D卷-200分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146262492
 */
public class OdMain {

    /**
     * 贪心算法，计算在最大工作量限制下所需的员工人数
     *
     * @param k    最大工作量
     * @param nums 任务工作量列表
     * @return 完成所有任务所需的最少员工人数
     */
    public static int check(int k, List<Integer> nums) {
        int left = 0, right = nums.size() - 1, ans = 0;

        // 采用贪心策略：尽量将任务分配给当前员工，直到达到最大工作量
        while (left <= right) {
            if (nums.get(left) + nums.get(right) > k) {
                // 如果当前任务无法和最重任务配对，则分配给右侧员工
                right--;
            } else {
                // 否则，分配给当前员工
                left++;
                right--;
            }
            ans++; // 每次分配任务，使用一个员工
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入任务数量 m
        int m = scanner.nextInt();

        // 读取每个任务所需的工作量
        List<Integer> nums = new ArrayList<>();
        while (scanner.hasNextInt()) {
            nums.add(scanner.nextInt());
        }

        // 对任务进行排序，以便从小到大进行贪心分配
        Collections.sort(nums);

        // 设置二分查找的范围，最小为最大工作量，最大为任务的总和
        int left = Collections.max(nums);
        int right = nums.stream().mapToInt(Integer::intValue).sum() + 1;

        // 二分查找最小的最大工作量
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(mid, nums) <= m) {
                right = mid; // 如果可以用 m 个员工完成，尝试更小的最大工作量
            } else {
                left = mid + 1; // 否则需要增大最大工作量
            }
        }

        // 输出最小的最大工作量
        System.out.println(left);
    }
}
